import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author LKQ
 * @date 2022/2/25 11:52
 * @description
 */
public class FormalSolution {
    public static void main(String[] args) {
        String s = "1231";
        s.con
    }
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 用hash表或计数节省排序时间
        Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        int ans = Arrays.stream(nums).sum();
        for (int i = -100; i < 0; ++i) {
            if (freq.containsKey(i)) {
                // 拥有次数和修改次数k作比较
                int ops = Math.min(k, freq.get(i));
                // 弥补加负数操作
                ans += (-i) * ops * 2;
                freq.put(i, freq.get(i) - ops);
                // 修改之后 负数变对应正数
                freq.put(-i, freq.getOrDefault(-i, 0) + ops);
                k -= ops;
                if (k == 0) {
                    break;
                }
            }
        }
        if (k > 0 && k % 2 == 1 && !freq.containsKey(0)) {
            // k 还有剩余并且为奇数，并且不包含0
            for (int i = 1; i <= 100; ++i) {
                if (freq.containsKey(i)) {
                    ans -= i * 2;
                    break;
                }
            }
        }
        return ans;
    }

}
